c_Comp-Prog RUPC2024 Day2 A Similar Routes
スライドだと文字数的に言葉足らずだったのと、現地解説普通に馬鹿下手だったのでscrapboxで補足します
問題
無向カクタスグラフが与えられます。ある一点において、その一点とあるもう一点を端とした二点間の最短パスと最長パスが一致する最大距離を全ての頂点に対して求めてください。
考察
定義
パスの長さ: パスに存在する頂点列の長さ
解説
カクタスグラフというのは意外に良い性質を持っています。
とりあえず適当に2点を選んで考えてみると、その2点を結ぶパスはカクタスグラフの性質から必ず同じ閉路を通ることがわかり、それは一般に言えることがわかります。また、その閉路の入口と出口も固定であることがわかります。(今回のグラフは無向なので入口と出口という言葉は適切ではないのですが、簡単のためにその用語を使います)
ここで、閉路の入口と出口が異なるとき、パスの性質から一つの閉路に対して通る道は時計回りか反時計回りで有ることが言えます。
どちらをたどっても他の閉路の動きに影響をもたらさないため、それぞれの閉路は独立に考えることができて、時計回りと反時計回りのパスの長さが一致するときは 閉路に存在する頂点の数が偶数 かつ 入口と出口を結ぶパスの長さが閉路に存在する頂点の数の半分+1 であるときのみであることが言えます。
また、閉路に属さない通常のパスはその辺を分断すると右グラフと左グラフが完全に分断されることから、その辺のみがパスに影響する辺であるためそのまま使っていいことがわかります。(ほぼ自明なので雑に書いてます)
よって、それぞれの辺に対して適切な重みを持つ辺を用意し新たなグラフを作成します。
そのようにして出来たグラフにおいて、同じ連結成分に存在する2点は必ず今回の問題の条件を満たすため、それぞれの連結成分においてそれぞれの頂点が持つ最長のパスを求めればいいことがわかります。
このとき、任意の頂点において最長のパスはある木の直径の端2点のうちどちらかとのパスが最長の長さになることがわかります。(この部分は少し知識だったかも 知識なくても全方位木DPでいけます)
よって木の直径となる2点をDFSで求め、その2点からDFSで任意の頂点への長さを記憶させ、その最大値を出力することで答えとなります。
与えられるグラフが連結とは限らないことに注意して実装してください。
実装 かなり雑なのであまり参考にしないでくれると助かります
code:solve.cpp
vector<int> route;
set<int> routeS;
vector<vector<int>> graph1;
vector<int> lck;
struct p{
int u,v;
bool operator<(const p x)const{
if(u == x.u)return v < x.v;
return u < x.u;
}
};
struct d{
p edge;
int dist;
};
vector<d> append;
set<p> remover;
void dfs1(int v, int p = -1){
for(size_t i = 0; graph1v.size() > i; i++){ if(graph1vi == p)continue; if(routeS.find(graph1vi) != routeS.end()){ vector<int> circle;
circle.push_back(graph1vi); circle.push_back(v);
for(size_t j = route.size()-1; routej != graph1vi; j--){ circle.push_back(routej); }
if(circle.size()%2 == 0){
for(size_t i = 0; circle.size()/2 > i; i++){
}
}
for(size_t i = 0; circle.size() > i; i++){
}
continue;
}
route.push_back(v);
routeS.insert(v);
route.pop_back();
routeS.erase(v);
}
}
}
struct b{
int n,dist;
bool operator<(const b x)const{
if(dist == x.dist)return n < x.n;
return dist < x.dist;
}
bool operator==(const b x)const{
return n == x.n && dist == x.dist;
}
bool operator>(const b x)const{
return !((*this)<x || (*this)==x);
}
};
vector<vector<b>> graph2;
set<int> lck1;
vector<int> ans;
int get_diameter(int x){
lck1.clear();
lck1.insert(x);
priority_queue<b, vector<b>, greater<b>> vs;
vs.push({x,0});
int ret = -1;
while(vs.size()){
auto v = vs.top(); vs.pop();
ret = v.n;
for(size_t i = 0; graph2v.n.size() > i; i++){ if(!lck1.count(graph2v.ni.n)){ lck1.insert(graph2v.ni.n); vs.push({graph2v.ni.n, v.dist+graph2v.ni.dist}); }
}
}
return ret;
}
void set_maxlen(const int &x){
lck1.clear();
lck1.insert(x);
priority_queue<b, vector<b>, greater<b>> vs;
vs.push({x,0});
while(vs.size()){
auto v = vs.top(); vs.pop();
for(size_t i = 0; graph2v.n.size() > i; i++){ if(!lck1.count(graph2v.ni.n)){ lck1.insert(graph2v.ni.n); vs.push({graph2v.ni.n, v.dist+graph2v.ni.dist}); ans[graph2v.ni.n] = max(ans[graph2v.ni.n], v.dist+graph2v.ni.dist); }
}
}
}
void calcdist(const int &n){
auto l = get_diameter(n);
auto r = get_diameter(l);
set_maxlen(l);
set_maxlen(r);
}
int main(){
int n,m;cin>>n>>m;
graph1.assign(n, vector<int>());
for(int i = 0; m > i; i++){
int u,v;cin>>u>>v;u--;v--;
}
lck.assign(n, false);
for(int i = 0; n > i; i++){
dfs1(i);
}
}
graph2.assign(n, vector<b>());
for(int i = 0; n > i; i++){
for(size_t j = 0; graph1i.size() > j; j++){ if(remover.find({i, graph1ij}) == remover.end()){ graph2i.push_back({graph1ij, 1}); graph2[graph1ij].push_back({i, 1}); }
}
}
for(size_t i = 0; append.size() > i; i++){
graph2[appendi.edge.u].push_back({appendi.edge.v, appendi.dist}); graph2[appendi.edge.v].push_back({appendi.edge.u, appendi.dist}); }
ans.assign(n, -1);
for(int i = 0; n > i; i++){
calcdist(i);
}
}
for(int i = 0; n > i; i++){
}
}
振り返り
exampleに非連結であるケースが存在しなかったのはかなり不親切でした ごめんなさい
書いてて思ったんだけど有向のカクタスグラフもなんか面白い性質がありそう generator作るのばり大変そうですが...
というわけでChallenge: 今回の問題を有向カクタスグラフに対して解いてください
これはこの問題に限らずなんですが、任意の問題に対して解説を書いてくれるとwriterは基本喜ぶと思っているので(少なくとも私は喜びます)、この問題に限らずいろいろな問題でユーザー解説を書いてくれると自分ごとのように喜びます
証明
暇なときやります 定義書くのが重いんだ
なんか用語定義wikiとかありませんか? mathworldとか?